/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/surrounded-regions
   @Language: C++
   @Datetime: 19-09-04 13:41
   */

class Solution {
	void dfs(vector<vector<char> > &board, int i, int j){
		int m=board.size(), n=board[0].size();
		if(i<0 || i>=m || j<0 || j>=n || board[i][j]=='X' || board[i][j]=='#') return;
		board[i][j]='#';
		dfs(board,i+1,j);
		dfs(board,i-1,j);
		dfs(board,i,j+1);
		dfs(board,i,j-1);
	}
public:
	void solve(vector<vector<char>>& board) {
		if(board.size()==0 || board[0].size()==0) return;
		int m=board.size(), n=board[0].size();
		for(int i=0; i<m; ++i){
			if(board[i][0]=='O') dfs(board,i,0);
			if(board[i][n-1]=='O') dfs(board,i,n-1);
		}
		for(int j=0; j<n; ++j){
			if(board[0][j]=='O') dfs(board,0,j);
			if(board[m-1][j]=='O') dfs(board,m-1,j);
		}
		for(int i=0; i<m; ++i)
			for(int j=0; j<n; ++j)
				if(board[i][j]=='O') board[i][j]='X';
				else if(board[i][j]=='#') board[i][j]='O';
	}
};
